package binarysearch;

/**
 * @description:
 * @author: jhy
 * @time: 2021/4/22 18:53
 */

//查找第一个大于等于给定值的元素
public class BinarySearchDemo5 {

    public static void main(String[] args) {

        int[] nums = {1,2,2,2,4,4,4,4,4,5,6};
        int i = binarySearch(nums, 3);
        System.out.println(i);


    }

    //思路：每次二分，如果nums[mid] < target，说明要找的值在mid右边，直接left = mid + 1;
    //否则，当前仅当mid == 0 || nums[mid - 1] < target，此时的mid是要找的索引
    //否则，当前找的mid不是第一个大于等于target的值，向左查找，即right = mid - 1;
    public static int binarySearch(int[] nums,int target){

        int left = 0;
        int right = nums.length - 1;
        while (left <= right){

            int mid = left + (right - left)/2;
            if(nums[mid] < target){ //要找的数据在mid的右边]
                left = mid + 1;
            }else {
                if(mid ==0 || nums[mid - 1] < target){ //mid为要找的位置
                    return mid;
                }
                //当前找到的mid不是第一个要找的，继续向左二分
                right = mid - 1;
            }
        }
        return -1;
    }
}
